/**
 * 记忆化的方式解决01背包问题 
 */
#include <bits/stdc++.h>
using namespace std;
int dp[100 + 2][1000+ 2];
int V[100 + 2], W[100 + 2];
int T, M;
int dfs(int i, int j)
{
    // printf("(%d,  %d)\n", i, j);
    // 剩余空间为0, 或到达叶子结点
    if(j <= 0 || i > M) return 0;

    // 取记忆化的值
    if(dp[i][j] != -1) return dp[i][j];
    
    if(j < W[i])
        return dp[i][j] = dfs(i + 1, j);
    else 
        return dp[i][j] = max(dfs(i + 1, j), dfs(i + 1, j - W[i]) + V[i]);
}
int main()
{
#ifdef LOCAL
    freopen("ALGO-30.in", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> T >> M;
    for(int i = 1; i <= M; ++i)
        cin >> W[i] >> V[i];
    int ret = dfs(1, T);
    cout << ret << endl;
    return 0;
}